package q827;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 827. 最大人工岛
 */
public class Solution {

    int maxArea = 0;
    Map<Integer, Integer> map = new HashMap<>();

    public int largestIsland(int[][] grid) {
        // 岛屿编号
        int islandNum = 2;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int area = dfsArea(grid, i, j, islandNum);
                    map.put(islandNum, area);
                    islandNum += 1;
                }
            }
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                   int area = 1;
                   Set<Integer> set = new HashSet<>();
                   if (i > 0 && grid[i - 1][j] >= 2) {
                       area += map.get(grid[i - 1][j]);
                       set.add(grid[i - 1][j]);
                   }
                   if (j > 0 && grid[i][j - 1] >= 2 && !set.contains(grid[i][j - 1])) {
                       area += map.get(grid[i][j - 1]);
                       set.add(grid[i][j - 1]);
                   }
                   if (i < grid.length - 1 && grid[i + 1][j] >= 2 && !set.contains(grid[i + 1][j])) {
                       area += map.get(grid[i + 1][j]);
                       set.add(grid[i + 1][j]);
                   }
                   if (j < grid[0].length - 1 && grid[i][j + 1] >= 2 && !set.contains(grid[i][j + 1])) {
                       area += map.get(grid[i][j + 1]);
                       set.add(grid[i][j + 1]);
                   }
                   maxArea = Math.max(area, maxArea);
                }
            }
        }

        if (grid[0][0] == 2 && maxArea == 0) {
            return grid.length * grid[0].length;
        }

        return maxArea;
    }

    public int dfsArea(int[][] grid, int i, int j, int islandNum) {
        if (!judge(grid, i, j)) return 0;
        int area = 1;
        grid[i][j] = islandNum;
        area += dfsArea(grid, i, j - 1, islandNum);
        area += dfsArea(grid, i, j + 1, islandNum);
        area += dfsArea(grid, i + 1, j, islandNum);
        area += dfsArea(grid, i - 1, j, islandNum);
        return area;
    }

    // 是否已经访问过
    public boolean judge (int[][] grid, int i, int j) {
        return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] == 1;
    }

    public static void main(String[] args) {
        int[][] grid = {{0, 0}, {0, 0}};
        Solution solution = new Solution();
        System.out.println(solution.largestIsland(grid));
    }
}
